#include "base.h"

class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int begin = 0, end = nums.size() - 1;

        while (begin <= end)
        {
            auto mid = (begin + end) / 2;

            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target) //中间值小于目标值，范围向右 begin 0| end 0
            {
                //begin -> 1
                begin = mid + 1;
            }
            else //中间值>目标值，范围向左 begin 0 |end 0
            {
                //end -> -1
                end = mid - 1;
            }
        }
        return begin;
    }
};